/************************************
作用：练习常见排序算法
https://blog.csdn.net/weixin_43872728/article/details/101039829
************************************/
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <string.h>
#include <vector>

using namespace std;

//交换两个元素的值
#define swap(a, b) do { /*  a和b不能指向同一对象 */\
  int temp = *(a);\
  *(a) = *(b);\
  *(b) = temp;\
} while(0)

//插入排序, 原地/稳定排序, time: O(n^2), space: theta(1)
void insert_sort(int array[] , int n) {
  int i,j,temp;
  for(i=1;i < n;i++) {
    temp = array[i];
    for(j=i-1;j>=0;j--) //[0,i-1]已排好序，可使用二分法和i比较来快速确定i的位置
      if(array[j] > temp) array[j+1] = array[j];
      else break;
    array[j+1] = temp;
  }
}
//交换插入排序--直接交换相邻元素代替移动
//原地/稳定排序，time: O(n^2), space: theta(1)
void swap_insert_sort(int array[], int n) {
  int i,j;
  for(i=1;i<n;i++)
    for(j=i-1;j>=0 && array[j]>array[j+1];j--)
      swap(array+j,array+j+1);
}

//二分插入排序, 原地/稳定排序, t: O(n^2), s: theta(1)
void dichotomy_insert_sort(int array[], int n) {
  int i;
  int left, right, mid;
  int j;
  int temp;
  for(i=1;i<n;i++) {
    temp = array[i];
    for(left=0,right=i-1;left<=right;) {
      mid = (right+left)/2;
      if(array[mid] > temp) right = mid-1;
      else left = mid+1;
    }//循环退出时left即为i的插入位置
    for(j=i;j>left;j--)
      array[j] = array[j-1];
    array[left] = temp;
  }
}

//递归版插入排序，原地/稳定排序，t: O(n^2), s: theta(n)
//递归调用次数: n-1
void r_insert_sort(int array[], int n) {
	if(n < 2) return;
	r_insert_sort(array, n-1);
	int i;
	int tmp = array[n-1];
	for(i=n-2; i>=0 && array[i]>tmp; i--) {
		array[i+1] = array[i];
	}
	array[i+1] = tmp; 

}

//冒泡排序: 原地/稳定排序，t: theta(n^2), s: theta(1)
//主要步骤：从头开始表较并相邻元素，通过交换将最值移动到最右短
void bubble_sort(int array[] , int n) {
  int i,j;
  int sorted;  //设置标识，判断是否已排好序
  for(i=n-1; i>0; i--){ //可以改写成双向的
    sorted = 1;
    for(j=0; j<i; j++)
      if(array[j] > array[j+1]) {
        swap(array+j,array+j+1);
        sorted = 0;
      }
    if(sorted) break; //如果子循环过程没有发生交换，则已排好序
  }
}

//选择排序, 原地/不稳定排序，t: theta(n^2), s: theta(1)
//每次交换时可能会打乱相同元素的相对位置，因此不稳定
void select_sort(int array[] , int n) {
  int i,j,min;
  for(i=0;i<n-1;i++) {
    min = i;
    for(j=i+1;j<n;j++)
      if(array[j] < array[min]) min=j;
    if(min != i) swap(array+i,array+min);
  }
}

//希尔排序(分组插入排序)，详细版
//原地/不稳定, t: O(n^2), s: theta(1), 估算时间复杂度时可将n看作2的k次方
//将整个数组分为gap(n/2->1)组, 第一组为(0, 0+gap, 0+gap+gap...)
//第二组(1, 1+gap, 1+gap+gap...)
//第三组(2, 2+gap...)
//第gap组(gap-1, gap-1+gap...) 
//各组的元素个数不一定相同, 且组内元素是等间隔分开的
//时间复杂度可优化到O(n^1.3)??
void shell_sort(int array[],int n) {
  int gap ; //分成的组数n/2->1， 每组的元素个数
  int i,j,k,temp;
  for(gap=n>>1; gap>0; gap>>=1)
    for(i=0;i<gap;i++) //i为各组首元素
      for(j=i+gap;j<n;j+=gap) { //j为当前分组准备插入的元素
        temp = array[j] ; 
        for(k=j-gap;k>=0 && array[k]>temp;k-=gap) 
          array[k+gap] = array[k];
        array[k+gap] = temp;
      }
}

//简洁版希尔排序: 各组并行交换式插入排序, 效率不变
//先插入每组的第1个，所有组第一个都插入后
//再插入每组的第2个元素
void short_shell_sort(int array[], int n) {
  int gap;
  int i,j;
  for(gap=n>>1;gap>0;gap>>=1) //循环取不同步长
    //从每组的第1个元素(0为首个)开始进行插入排序
    //第1个元素都插入完毕后，自动变为第2个
    //相当于将详细版的第2和第3层for循环合并
    for(i=gap;i<n;i++) 
      for(j=i-gap;j>=0;j-=gap) 
        if(array[j] > array[j+gap]) //直接把新的小元素和该组已排序元素交换
          swap(array+j,array+j+gap);
}

//归并排序, out-palce/可稳定排序, t: theta(n*lg(n)), s: theta(n)
//递归实现--递归分组,直到只有一个元素,直接使用merge合并,再递归合并
//merge: 用于归并已排序好的两个子组array[0~left-1],array[left~right]
void merge(int array[], int tarray[], int left,int right) { 
  int *larray = array;
  int *rarray = array+left;
  int i=0,j=0,k=0;
  while( i<left&&j<right) {
    if(larray[i]<=rarray[j]) tarray[k++] = larray[i++];
    else tarray[k++] = rarray[j++];
  }
  while(i<left) tarray[k++] = larray[i++];
  while(j < right) tarray[k++] = rarray[j++];
  for(i=0; i<k; i++) {
    array[i] = tarray[i];
  }
}
void recursion_merge_sort_core(int array[], int tarray[], int n) {
  if(n<2) return;
  int left = n/2;
  int right = n-left;
  recursion_merge_sort_core(array, tarray, left);
  recursion_merge_sort_core(array+left, tarray, right);
  merge(array, tarray, left, right);
}
void recursion_merge_sort(int array[], int n) {
    int *tarray = new int[n];
    recursion_merge_sort_core(array, tarray, n);
    delete [] tarray;
}
//循环实现: 组长i从1到至多n/2，循环分组，每次分组后两两合并
//总长n = i*k+x, k>0表示完整的组数, x>=0, 表示余数
void loop_merge_sort(int array[],int n) {
  int i;
  int j;
  int *tarray = new int[n];
  for(i=1;i<=n/2;i*=2) {  //循环分组，组长从1递增到至多n/2(至少能完成一次对称合并)
    for(j=0;j+i*2 <= n;j+=i*2)  //两组一合并，直到剩余元素不够两组
      merge(array+j, tarray, i, i);
    if(j+i<n) merge(array+j, tarray, i, n-j-i); //合并剩余的（1组+x）元素
  }
  if(i<n) merge(array, tarray, i, n-i); //最后的组长不恰好为总长，则进行最后一次合并
}


/***********************
堆排序: 原地/不稳定!!, t: n*lg(n), s: theta(lg(n)), 估算时间复杂度时将数组看作一个高
    度为h的完全二叉树：n = 2^h-1
主要思想：将数组抽象为完全二叉树。将该树调整成大顶堆，然后从顶点取最值(暗含选择
    排序, 只不过取最值的方法不同)
完全二叉树:严格按照从左向右广度优先的方式展开
    将顶点看作0层0个，则k层首个为第2^0+..2^(k-1)+1-1=2^k-1个）
    因此父节点，左子节点和右子节点的序数满足lchildS = 2*pS+1,rchildS = lchildS+1
    因此序号为cS的节点的父节点的序号为(cS-1)/2
大顶堆：完全二叉树且父节点不小于子节点
***********************/
//对新的子树进行递归调整,使之符合大顶堆
//root: 为子树的顶点对应的索引，由于要向下调整，root不一定有子结点!!
//a: 待排序数组
//n: a的元素个数
//可以改写为尾递归的形式
void heap_adj(int a[], int root, int n) {  
    int m = root;
    int lc = root*2+1;
    int rc;
    while(lc < n) {
        if(a[lc] > a[m]) m = lc;
        rc = lc+1;
        if(rc<n && a[rc] > a[m]) m = rc;
        if(m == root) {
            break;
        }else {
            swap(a+m, a+root);
            root = m;
            lc = root*2+1;
        }
    }
}
void recursion_heap_adj(int a[], int root, int n) {  
    int m = root;
    int lc = root*2+1;
    if(lc >= n) return;
    if(a[lc] > a[m]) m = lc;
    int rc = lc+1;
    if(rc<n && a[rc] > a[m]) m = rc;
    if(m != root) {
        swap(a+m, a+root);
        recursion_heap_adj(a, m, n);
    }
}

//堆排序主函数
void heap_sort(int array[],int n) {
  int root = (n-1-1)/2;  //找到倒数第一个顶点（(end_cS-1)/2）
  //依次调整所有顶点使未排序的元素构成的子树满足大顶堆
  //第一个顶点元素及其前面都可以看作顶点
  for(; root>0; root--) 
#ifdef RECURSION
    recursion_heap_adj(array, root, n); 
#else
    heap_adj(array, root, n); 
#endif
    
  while(n>1) {
#ifdef RECURSION
    recursion_heap_adj(array, root, n); 
#else
    heap_adj(array, root, n); 
#endif
    swap(array,array+n-1); //从堆顶（array[0]）取出最大值
    n--;
  }
}

//快速排序, 原地/不稳定, t: omiga(n*lg(n)), s: 递归带来的开销:: omiga(lg(n))
void quick_sort(int array[],int n) {
  if (n<2) return;
  int i=1,j=n-1;
  while(i<j) {
    while(i<j && array[i]<=array[0])
      i++;
    while(j>i && array[j]>=array[0])
      j--;
    if(i<j) {
      swap(array+i, array+j);
      i++;
      i<j && j--;
    }
  }
  //此时i=j
  if(array[i]>array[0]) {
    i--;
  }
  if(i) swap(array, array+i);
  quick_sort(array,i);
  quick_sort(array+i+1,n-i-1);
}


/**************************
桶排序: out-place/稳定排序：t: theta(d+n), d为最值差+1, s: theta(d+n)
核心思想：以数组的最值为桶边界，利用桶存储hash值相同的元素
桶：用来存储原数组中hash值相同的元素的动态数组，其中桶的索引对应着原数组元素的值
**************************/
void bucket_sort(int array[], int n) {
  int i, minv, maxv;
  if(n<2) return;
  minv = array[0]; maxv = array[0];
  for(i=1;i<n;i++) {  //获得最大值和最小值
    if(minv > array[i]) minv = array[i];
    else if(maxv < array[i] ) maxv = array[i];
  }
  int len = maxv - minv + 1;
  vector<vector<int>>obucket(len);
  for(i=0;i<n;i++)
    //array[i]-minv即为该元素的哈希值
    obucket[array[i]-minv].push_back(array[i]); 
  int top=0;
  vector<int>::iterator vit;
  for(i=0;i<len;i++) {
    for(vit = obucket[i].begin(); vit != obucket[i].end(); vit++) {
        array[top++] = *vit;
    }
  }
}

/***********************************
基数排序: out-place(基于桶排序)/稳定排序, t: O(m*(d+n)), s: O(d+n)
主要步骤：将用于排序的比较过程拆分为多个比较因子，依次针对每个因子(先排序优先级低的)进行排序。
时间效率：设待排序列为n个记录，m个比较因子，每个比较因子的hash值范围为d
    则进行链式基数排序的时间复杂度为O(m*(d+n))
***********************************/
//针对当前比较因子进行排序，且保持稳定性，方法不固定，这里采用特殊的桶排序
void count_sort(int array[], int tarray[], int n, int exp) {
    //比较因子： 元素的第(从0开始)log(10, exp)位。
    //元素在该比较因子下的hash值为: array[i]/exp%10
    int bucket[10] = {0}; //针对该比较因子有限的10种情况
    int i;
    for(i=0;i<n;i++)
        bucket[array[i]/exp%10]++;
            //bucket[k]: 当前比较因子下哈希值为k的元素的个数
    for(i=1;i<10;i++)
        bucket[i] += bucket[i-1]; 
        //bucket[i]: 该比较因子下hash值为0到i的元素的个数
    for(i=0;i<10;i++)
        bucket[i]--;   
        //bucket[i]: 仅基于该比较因子进行排序，hash值为i的元素在排序后的最大索引
    //通过bucket记录的最大index,把相应的值依次存入临时数组
    for(i=n-1;i>=0;i--) 
        //采用降序使key值相同时原本靠后的元素依旧靠后，保持稳定性
        tarray[bucket[array[i]/exp%10]--] = array[i]; 
    for(i=0;i<n;i++)
        array[i] = tarray[i];
}
//调用count_sort依次针对不同级别的key进行排序
void radix_sort(int array[], int n) {  //array[i] >= 0!!
  int max = array[0];
  int i;
  for(i=1;i<n;i++)
    if(max<array[i])
      max = array[i];
  for(i=1;max/=10;i++) //获取max位数i:个数
    ;
  int exp;
  int *tarray = new int[n];
  for(exp=1;i--;exp*=10) //移动0,n-1位:LSD,不可以MSD
    count_sort(array, tarray, n, exp);
  delete [] tarray;
}


//***************测试代码**************************
//打印数组
void printarray(int array[],int n) {
  int i;
  for(i=0;i<n;i++) printf("%d\n",array[i]);
}

//统一测试函数
void testf(void (*fuc)(int *, int),int array[],int n, char const *fucname) {
  struct timeval tv;
  int i;
  gettimeofday(&tv,NULL);
  double start = tv.tv_sec + tv.tv_usec/1000000.0;
  fuc(array,n);
  gettimeofday(&tv,NULL);
  double end = tv.tv_sec + tv.tv_usec/1000000.0;
  for(i=1; i<n; i++) {
    if(array[i]<array[i-1]) {
        printf("%25s: 算法有误!\n", fucname);
        return;
    }
        
  }
  printf("%25s: %.6fs\n",fucname,end-start);
}

int main()
{
  int n = 5120;
#ifdef DOUBLE
    n *= 2;
#endif
  printf("num to sort:%d\n",n);
  int *array = new int[n]; 
  if(array == NULL) return -1;
  srand(time(NULL));
  int i;
  for(i=0;i<n;i++)
    array[i] = rand()%n;
  
  int *temp = new int[n];
  if(temp == NULL) return -1;

  memcpy(temp,array,sizeof(int)* n);
  testf(insert_sort,temp,n,"insert_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(r_insert_sort,temp,n,"r_insert_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(swap_insert_sort,temp, n,"swap_insert_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(dichotomy_insert_sort,temp,n,"dichotomy_insert_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(bubble_sort, temp, n, "bubble_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(select_sort,temp,n,"select_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(short_shell_sort,temp,n,"short_shell_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(shell_sort,temp,n,"shell_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(recursion_merge_sort,temp,n,"recursion_merge_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(loop_merge_sort,temp,n,"loop_merge_sort"); 
  memcpy(temp,array,sizeof(int)* n);
  testf(heap_sort,temp,n,"heap_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(quick_sort,temp,n,"quick_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(bucket_sort,temp,n,"bucket_sort");
  memcpy(temp,array,sizeof(int)* n);
  testf(radix_sort,temp,n,"radix_sort");
  //printarray(temp,n);

  delete [] array;
  delete [] temp;
  return 0;
}
/************************************************/
